package com.liufei.class04;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;

public class Code03_DoubleLinkedListToDeque {

    public static class DoubleNode<V> {

        V value;

        DoubleNode<V> last;

        DoubleNode<V> next;

        public DoubleNode(V value) {
            this.value = value;
        }
    }

    public static class MyDeque<V> {

        DoubleNode<V> head;

        DoubleNode<V> tail;

        int size = 0;

        public MyDeque() {
            head = null;
            tail = null;
            size = 0;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public int size() {
            return size;
        }

        public void pushHead(V value) {
            DoubleNode<V> cur = new DoubleNode<>(value);
            if (head == null) {
                head = cur;
                tail = cur;
            } else {
                cur.next = head;
                head.last = cur;
                // 别忘记移动head指针
                head = cur;
            }
            size++;
        }

        public void pushTail(V value) {
            DoubleNode<V> cur = new DoubleNode<>(value);
            if (head == null) {
                head = cur;
                tail = cur;
            } else {
                tail.next = cur;
                cur.last = tail;
                // 别忘记移动tail指针
                tail = cur;
            }
            size++;
        }

        public V pollHead() {
            if (head == null) {
                return null;
            }
            V ans = head.value;
            size--;
            if (head == tail) {
                // 只有一个元素
                head = null;
                tail = null;
            } else {
                head = head.next;
                head.last = null;
            }
            return ans;
        }

        public V pollTail() {
            if (head == null) {
                return null;
            }
            size--;
            V ans = tail.value;
            if (head == tail) {
                // 只有一个元素
                head = null;
                tail = null;
            } else {
                // tail往前移动
                tail = tail.last;
                tail.next = null;
            }
            return ans;
        }

        public V peekHead() {
            if (head == null) {
                return null;
            }
            return head.value;
        }

        public V peekTail() {
            if (tail == null) {
                return null;
            }
            return tail.value;
        }
    }


    public static void main(String[] args) {
        Deque<Integer> deque = new ArrayDeque<>();
        MyDeque<Integer> deque1 = new MyDeque<>();
        int testTime = 10000;
        int maxValue = 20000;
        System.out.println("测试MyDeque开始！");
        for (int i = 0; i < testTime; i++) {
            if (deque1.isEmpty() != deque.isEmpty()) {
                System.out.println("Oops!");
            }
            if (deque1.size() != deque.size()) {
                System.out.println("Oops!");
            }
            double decide = Math.random();
            if (decide < 0.33) {
                int num = (int) (Math.random() * maxValue);
                if (Math.random() < 0.5) {
                    deque.addFirst(num);
                    deque1.pushHead(num);
                } else {
                    deque.addLast(num);
                    deque1.pushTail(num);
                }
            } else if (decide < 0.6) {
                if (!deque1.isEmpty()) {
                    // 这里要加空判断，不然poll拿出的数据是null，不能直接转成 int 类型
                    if (Math.random() < 0.5) {
                        int num1 = deque.pollFirst();
                        int num2 = deque1.pollHead();
                        if (num1 != num2) {
                            System.out.println("Oops!");
                        }
                    } else {
                        int num1 = deque.pollLast();
                        int num2 = deque1.pollTail();
                        if (num1 != num2) {
                            System.out.println("Oops!");
                        }
                    }
                }
            } else {
                if (!deque1.isEmpty()) {
                    // 这里要加空判断，不然poll拿出的数据是null，不能直接转成 int 类型
                    if (Math.random() < 0.5) {
                        int num1 = deque.peekFirst();
                        int num2 = deque1.peekHead();
                        if (num1 != num2) {
                            System.out.println("Oops!");
                        }
                    } else {
                        int num1 = deque.peekLast();
                        int num2 = deque1.peekTail();
                        if (num1 != num2) {
                            System.out.println("Oops!");
                        }
                    }
                }
            }
        }
        if (deque1.size() != deque.size()) {
            System.out.println("Oops!");
        }
        while (!deque1.isEmpty()) {
            int num1 = deque1.pollHead();
            int num2 = deque.pollFirst();
            if (num1 != num2) {
                System.out.println("Oops!");
            }
        }
        System.out.println("测试MyDeque结束！");
    }
}
